package ljl.codetop300;

/**
 * 这个题有三个难点：
 * 1. k 一上来就得 --
 * 2. 求 step 时得用 long
 * 3. 题目本身就很难，普通人绝无可能做出来
 */
public class _440_find_kth_number {

  static class off {
    public int findKthNumber(int n, int k) {
      int curr = 1;
      k--;
      while (k > 0) {
        int steps = getSteps(curr, n);
        // 孩子不够多，去折磨下一位
        if (steps <= k) {
          k -= steps;
          curr++;
        }
        // 孩子足够多，从给一个孩子开始找
        else {
          curr = curr * 10;
          k--;
        }
      }
      return curr;
    }

    /**
     * steps 是某个节点下面有几个孩子
     */
    public int getSteps(int curr, long n) {
      int steps = 0;
      long first = curr;
      long last = curr;
      // 第一个孩子比 n 大说明孩子太多了
      while (first <= n) {
        // 总数怎么算？当前层，最后一个 - 第一个 + 1
        steps += Math.min(last, n) - first + 1;
        // 去下一层，这个关系很关键，不好想。想出来，诺奖给你
        first = first * 10;
        last = last * 10 + 9;
      }
      return steps;
    }
  }

  static class test {
    public int findKthNumber(int n, int k) {
      int current = 1;
      k--;
      while (k > 0) {
        int childrenCount = childrenCount(current, n);
        if (childrenCount <= k) {
          current++;
          k -= childrenCount;
        } else {
          current *= 10;
          k--;
        }
      }
      return current;
    }

    /**
     * 这还有坑：计算的时候需要用 long 不然会溢出
     */
    int childrenCount(int from, long total) {
      int count = 0;
      long firstChild = from;
      long lastChild = from;
      while (firstChild <= total) {
        count += Math.min(lastChild, total) - firstChild + 1;
        firstChild = firstChild * 10;
        lastChild = lastChild * 10 + 9;
      }
      return count;
    }
  }
}
